/**
 * @author João Luís Palma Cardeira - hippie.stereo@gmail.com
 * @version 1.0
 * @date 06/06/2013
 * @copyright (C) :-)
 * @note Applicação para o trabalho de EDA 2012/2013
 * @see main : RunApp
 */
class MergeSortCLS
{

	/** 
	 * nomMethode - XXX
	 * @return [description]
	 * @param [parameter-name] [description]
	 * @param [parameter-name] [description]
	 * @exception   Exception1  description de la première exception 
	 * @see UneAutreClasse#UneAutreMethode 
	 */
	
	protected void MergeSort(double[] listaIn, int posBegin, int posEnd)
	{		
		if(posBegin < posEnd)
		{
			int posMid = (posBegin + posEnd) / 2; 
			MergeSort(listaIn, posBegin, posMid);
			MergeSort(listaIn, (posMid + 1), posEnd);
			Merge(listaIn, posBegin, posMid, posEnd);
		}
	}

	/** 
	 * nomMethode - XXX
	 * @return [description]
	 * @param [parameter-name] [description]
	 * @param [parameter-name] [description]
	 * @exception   Exception1  description de la première exception 
	 * @see UneAutreClasse#UneAutreMethode 
	 */
	
	private void Merge(double[] listaIn, int posBegin, int posMid, int posEnd)
	{	
		int posLeft = posMid - posBegin + 1;
		int posRight = posEnd - posMid;
		
		double[] listLeft = new double[posLeft + 1];
		double[] listRight = new double[posRight + 1];
		
		for (int i = 0; i < posLeft; i++)
		{
			listLeft[i] = listaIn[(posBegin + i) - 1];
		}
		
		for (int i = 0; i < posRight; i++)
		{
			listRight[i] = listaIn[posMid + i];
		}
		
		listLeft[posLeft] = 666;
		listRight[posRight] = 666;
		
		int keyLeft = 0;
		int KeyRight = 0;
		
		for (int i = posBegin - 1; i < posEnd; i++)
		{
			if(listLeft[keyLeft] <= listRight[KeyRight])
			{
				//double temp = listaIn[i];
				listaIn[i] = listLeft[keyLeft];
				//listLeft[keyLeft] = temp;
				keyLeft += 1;
			}
			else
			{
				//double temp = listaIn[i];
				listaIn[i] = listRight[KeyRight];
				//listRight[KeyRight] = temp;
				KeyRight += 1;
			}
		}
	}
}